The field to which the invention applies is the electronic processing of graphic images to produce multi-color output using offset or other printing methods. Images are obtained electronically by digital scanning of photographic material and combined with "structured graphics" to provide composed images or pages which are then separated into monochromatic images each corresponding to an ink to be used in the printing process. Typically, four process color inks, cyan, magenta, yellow and black are used, although special "spot" colors can be used instead of or in addition to the process color inks. The separated images can then be output to photographic films from which printing plates are made. Alternatively, the separated images can be used to produce engraved cylinders from which gravure prints can be made.
The layout of a page or graphic image to be printed as described above depends upon combination of "structured graphics" according to a pre-established graphic design. The structured graphics are contiguous regions of color which represent a succession of graphic objects imaged on the printing medium (e.g. the "paper"). The objects so imaged are polygon shapes which can be isolated from each other, can abut one another at one or more points, can partially overlap one another, or can completely overlap one another. The resulting printed page or graphic image is therefore made up of a patchwork of polygon shapes representing the graphic objects, some of which are "clipped" by objects imaged later in the succession.
The result of abutting or overlapping polygon shapes is a boundary between adjacent regions of color which under ideal printing conditions should have zero width. The "colors" which fill the polygon shapes can be solid colors, tints, degrades, contone images, or "no fill" (i.e., the paper with no ink applied). In general, the "colors" represented in these adjacent regions are printed using more than one ink. In practice therefore, the realization of a zero width boundary between regions of different color is impossible as a result of small but visible misregistration problems from one printing plate to another. The error is manifested as a "light leak" or as a visible boundary of an undesired color.
Methods for correcting for this misregistration are well known in the prior art. The general approach is to expand one of the regions which abut so as to fill the gap or misregistration border region with a color determined so as to minimize the visual effect when printed. Borders which are expanded from a region of one color to another in this manner are said to be "spread". A border which has been so expanded is referred to as a "trap", and the zone within which color is added is called the "trap zone".
Commonly used methods for automatic trapping of digital images rely on images which have been first scanned and are stored internally as a sequence of (high resolution) scan lines each containing individual scan elements or pixels. These methods process each raster line in sequence and compare one or more adjacent pixels to determine color boundaries, and apply rules for determining whether or not to create a trap at such boundaries, and finally apply a second set of rules to determine the nature of the trap if one is to be created.
For example, the method of Taniguchi, described in U.S. Pat. No. 4,931,861, uses two rasterized images representing abutting or overlapping objects within an image field to define a third binary image representing the map of the pixels which make up the borders between the first and second images. These three images are superimposed, pixel by pixel, to create a fourth and final binary image. The method of Hennig et al., described in U.S. Pat. No. 4,583,116 is also defined on a pixel basis, in as much as the images described are obtained by opto-electrical scanning source images. The patent also teaches a method for determining the boundary color for the (pixel-based) boundary separating the color regions. The method of Darby et al., described in U.S. Pat. No. 4,725,966, again defined on a pixel basis, uses a mask which is moved, one resolution element at a time, to evaluate the presence or absence of (pixel) colors upon which a positive or negative spread decision is based.
The method of Yosefi, described in U.S. Pat. No. 5,113,249 uses a set of automated rules as the basis for deciding, for each pair of abutting or overlapping shapes whether or not to create a trap (an overlap region referred to as a "frame"), and, if so, the nature of the trap to create. The preferred embodiment described by Yosefi makes use of scanned data, and processes each line of pixels in order, comparing for each pixel three pixels from the previous scan line and two pixels from the same line to determine if a color change has occurred. The decisions regarding whether or not to create a trap, and the nature of such a trap if created are imbedded within the processing sequence, making use of criteria established prior to the onset of processing.
A commercially available product, "Trap Wise", from Aldus Corporation, Seattle Wash., also makes use of a raster approach to trapping. In this product, the processing time is proportional to the number of resolution elements, thereby increasing quadratically with resolution, and leading to greater computation times for high device resolution, e.g., 3600 dots per inch (d.p.i.). Furthermore, traps are created with this package using pre-set rules, and are not editable by a user without the requirement for repeating the computation.
The trapping methods described in the above cited prior art references have two common features: The first is the processing of images represented in raster form. This places a requirement for extra processing steps in images which constitute primarily structured graphics or which combine structured graphics with contone images. Such images must first be rasterized at the output resolution, and then the appropriate line-scan algorithm applied. As a result of the number of edge boundaries involved (at output resolutions of for example 3600 d.p.i.), a substantial amount of redundant computation is required, particularly if a trap is created at each edge.
The second common feature of prior art methods is the necessity to make and apply trapping decisions within the processing based upon pre-established criteria. For raster based processing at high output device resolution, the potential number of pixel-to-pixel color transitions is large due to repetition of transitions corresponding to a single color region border shared by many scan lines. In U.S. Pat. No. 5,113,249, the decision to make a trap is conditional, so the number of color pairs to be considered is reduced below that which would be required if all color pairs were automatically trapped. Since the decision to make a trap is applicable only to generic color pairs encountered within a particular image, only color pairs processed in the first pass through the raster data can be subject to modification without reprocessing the raster at least once. To address other color pairs (i.e., to repeat the decision process), another pass is required. The method of the above patent does not therefore permit interactive modification and display of trapping decision modifications, since iterative application or modification of trapping decision rules is impractical when processing must generally be repeated (at least once through the entire raster) with each change.
Many rule-based methods exist in the prior art for automatic determination of the particular trap to be specified for a given combination of bounding colors. For example, in U.S. Pat. No. 5,113,249, a set of logical tests is used in sequence to differentiate between pre-established generic color-pair categories, with a rule applied to each color pair. Such built-in rule systems attempt to replicate the human aesthetic judgement used in manual specification of traps and each can provide results satisfactory to an "expert" user in most cases while failing to do so in other special situations. Without a means for configuring the automatic trap selection method, a user is forced to rely on manual trap specification, even for routine operations.
The specification of a trap at the boundary between two color regions does not in itself eliminate the misregistration of printing plates, but reduces the visual effect of misregistration within the trap zone through proper choice of the trap operation. In the event of plate misregistration involving a color separation for which a trap has been specified, additional "secondary" effects occur. The methods described in the prior art provide no information from which such efforts can be visualized during the process of trap specification, and therefore necessitate a "trial and error" approach.
It is therefore a general object of the present invention to permit the direct processing of structured graphic objects of an original image without the requirement for an initial rasterization process to specify trap characteristics at the boundaries between clipping or abutting regions of color considered as adjacent polygons each made up of a path of sequential line segments and filled by a solid color, a tint, a degrade, a contone image, or no fill (the blank "paper"), thereby producing a graphic image containing all such boundaries of the original image.
It is a further object of the present invention to generate a graphic image containing all boundaries of the original image in such a manner that its basic geometry is independent of any decisions regarding whether or not traps between individual regions are necessary, or the nature of such traps, thereby providing a wide range of options based upon pre-established rules or direct user interaction which can be applied iteratively without the necessity for recomputing the aforementioned geometry.
It is a further object of the invention to provide a system which allows trapping of document pages and images on a production basis with a user interface permitting display of the trapped and untrapped data, and the selection of trap decision methods ranging from fully automatic to completely manual interactive modes.
It is a still further object of the invention to permit the user of a trapping system to employ graphic user interface tools for direct manipulation of the borders between adjacent color regions on a trial basis and to observe the effects of such manipulation without the necessity of recomputing the aforementioned graphic image containing all boundaries of the original image, and before committing to the final output processing of the data being manipulated.
It is a still further object of the invention to include in the user interface of a trapping system an indication for any selected color region bounding other color regions a display of all possible effects of misregistration of printing plates which can occur for the selected color region as a result of no trapping, and as a result of any candidate trapping decision applied to all boundaries of the selected color region.
It is a still further object of the invention to include in the user interface of a trapping system an indication for any selected boundary between adjacent color regions a display of all possible secondary misregistration effects which would result from any candidate trapping decision.
It is a still further object of the invention to provide automatic specification of traps by user selection from more than one trap selection methods, or use of a combination of more than one trap selection method, based upon aesthetic judgement or special situations.
It is a feature of the present invention that the processing time required for generation of the trapping map is in general reduced in comparison to raster methods carried out at high device resolution, since the number of boundaries grows linearly with resolution while the number of pixels to be scanned in a raster grows quadratically.